/*
 * Copyright (C) 2025 Tsingteng MicroSystem
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#ifndef _PRIORITY_QUEUE_H_
#define _PRIORITY_QUEUE_H_

/**
 * @file  priority_queue.h
 * @brief 优先级队列结构及API函数声明
 * @date  2024-04-11
*/

#include <stdint.h>
#include <stdbool.h>
#include <stddef.h>

/** @brief 队列优先级类型 */
typedef uint64_t tQUEUE_PRIORITY;
/** @brief 队列元素ID类型 */
typedef uint32_t tQUEUE_ID;
/** @brief 队列元素TAG类型 */
typedef uint32_t tQUEUE_TAG;

/** @brief 队列元素节点结构体定义 */
typedef struct tQUEUE_NODE {
    /** @brief 下一个节点指针 */
    struct tQUEUE_NODE *next;
    /** @brief 保存的数据指针 */
    void *data;
    /** @brief 此节点优先级 */
    tQUEUE_PRIORITY priority;
    /** @brief 此节点ID, 此ID在队列中是唯一的 */
    tQUEUE_ID id;
    /** @brief 此节点TAG, 多个节点可以有相同的TAG */
    tQUEUE_TAG tag;
} tQUEUE_NODE;

/**
 * @brief 元素优先级比较函数，在插入元素时会被调用
 * @param inserted 被插入的元素的优先级
 * @param compared 队列中被比较元素的优先级
 * @return 1.当被插入元素的优先级满足插入条件时，返回大于0的数
 *         2.当被插入元素的优先级不满足插入条件时，返回小于0的数
 *         3.当被插入元素的优先级和队列中元素的优先级相等时，返回0
 * @code
 * 1.实现最小优先级队列（priority最小的排在最前面）时，函数实现应该是：compared - inserted
 * 2.实现最大优先级队列（priority最大的排在最前面）时，函数实现应该是：inserted - compared
 * @endcode
*/
typedef int64_t(*tQUEUE_COMP)(tQUEUE_PRIORITY inserted, tQUEUE_PRIORITY compared);

/**
 * @brief 元素被移除时的清理函数，在@see::pq_deinit @see::pq_remove_all @see::pq_clear 这类会移除多个元素且不会返回data指针的函数中会被调用
 * 此函数用于队列使用者自己管理节点数据的释放
 *
 * @param id 被删除的元素id
 * @param tag 被删除的元素的tag
 * @param data 被删除的元素包含的data指针（需要实现对此数据的释放）
*/
typedef void(*tQUEUE_CLEANUP)(tQUEUE_ID id, tQUEUE_TAG tag, void* data);

/**
 * @brief 遍历元素时传递的函数指针，在pq_foreach函数中需要用到
 *
 * @param index 当前遍历的第几个节点，从0开始计数，不会大于queue->size
 * @param id       当前节点的id
 * @param tag      当前节点的tag
 * @param priotity 当前节点的优先级
 * @param data     当前节点的数据指针
*/
typedef bool(*tQUEUE_FOREACH)(size_t index, tQUEUE_ID id, tQUEUE_TAG tag, tQUEUE_PRIORITY priotity, const void *data);

/** @brief 优先级队列结构体定义 */
typedef struct {
    /** @brief 队列首节点指针 */
    tQUEUE_NODE *root;
    /** @brief 队列元素优先级对比函数指针，在插入元素时使用 */
    tQUEUE_COMP comp;
    /** @brief 队列元素被移除时的清理函数指正，在@see::pq_deinit @see::pq_remove_all @see::pq_clear 中会被调用 */
    tQUEUE_CLEANUP cleanup;
    /** @brief 队列中元素的数量 */
    size_t size;
    /** @brief 队列插入元素时使用的基准id */
    tQUEUE_ID base_id;
} tPRIORITY_QUEUE;

/**
 * @brief 优先级队列提供的默认最小优先级对比函数
 *
 * 用于实现最小优先级队列。
 *
 * @param inserted 被插入队列的元素的优先级
 * @param compared 要比较的元素的优先级
 *
 * @return 1.当被插入元素的优先级满足插入条件时，返回大于0的数
 *         2.当被插入元素的优先级不满足插入条件时，返回小于0的数
 *         3.当被插入元素的优先级和队列中元素的优先级相等时，返回0
 */
int64_t pq_comp_min(tQUEUE_PRIORITY inserted, tQUEUE_PRIORITY compared);

/**
 * @brief 优先级队列提供的默认最大优先级对比函数
 *
 * 用于实现最小优先级队列。
 *
 * @param inserted 被插入队列的元素的优先级
 * @param compared 要比较的元素的优先级
 *
 * @return 1.当被插入元素的优先级满足插入条件时，返回大于0的数
 *         2.当被插入元素的优先级不满足插入条件时，返回小于0的数
 *         3.当被插入元素的优先级和队列中元素的优先级相等时，返回0
 */
int64_t pq_comp_max(tQUEUE_PRIORITY inserted, tQUEUE_PRIORITY compared);

/**
 * @brief 默认清理函数
 *
 * 当队列项不再需要时，调用此函数进行清理。
 *
 * @param id 队列ID
 * @param tag 队列标签
 * @param data 队列项数据指针
 */
void pq_default_cleanup(tQUEUE_ID id, tQUEUE_TAG tag, void *data);

/**
 * @brief 初始化优先级队列
 *
 * 初始化给定的优先级队列，并使用给定的比较函数和清理函数。
 * @note 初始化后，队列为空。
 * @note 传入的queue必须是未初始化过的队列，否则会导致内存泄漏。
 *
 * @param comp 比较函数指针
 * @param cleanup 清理函数指针
 *
 * @return 初始化成功返回 true，否则返回 false
*/
bool pq_init(tPRIORITY_QUEUE *queue, tQUEUE_COMP comp, tQUEUE_CLEANUP cleanup);

/**
 * @brief 销毁优先级队列
 *
 * 销毁给定的优先级队列，并释放相关资源。
 *
 * @note 可以通过free_data参数控制是否释放队列中数据的内存。但是不会释放队列本身的内存，即queue指针对应的内存。
 *
 * @param queue 优先级队列指针
 * @param free_data 是否释放队列中数据的内存
 *
 * @return 如果销毁成功，则返回 true；否则返回 false
 */
bool pq_deinit(tPRIORITY_QUEUE* queue, bool free_data);

/**
 * @brief 将数据加入优先级队列
 *
 * 将给定的数据加入优先级队列中，并根据优先级和标签进行排序。
 *
 * @param queue 优先级队列指针
 * @param data 数据指针
 * @param priority 优先级
 * @param tag 标签
 * @param id 节点ID指针
 *
 * @return 成功返回true，否则返回false
 */
bool pq_enqueue(tPRIORITY_QUEUE* queue, void* data, tQUEUE_PRIORITY priority, tQUEUE_TAG tag, tQUEUE_ID *id);

/**
 * @brief 从优先级队列中出队
 *
 * 从给定的优先级队列中移除并返回队首元素。
 *
 * @param queue 优先级队列指针
 *
 * @return 队首元素指针，如果队列为空或指针为NULL则返回NULL
 */
void *pq_dequeue(tPRIORITY_QUEUE* queue);

/**
 * @brief 从优先级队列中移除指定 ID 的节点
 *
 * 从给定的优先级队列中移除指定 ID 的节点，并返回该节点的数据指针。
 *
 * @param queue 优先级队列指针
 * @param id 要移除的节点的 ID
 *
 * @return 成功移除的节点的数据指针，若未找到则返回 NULL
 */
void *pq_remove(tPRIORITY_QUEUE *queue, tQUEUE_ID id);

/**
 * @brief 从优先级队列中删除所有指定TAG的节点
 *
 * 从给定的优先级队列中删除所有具有指定TAG的节点，并返回被删除节点的数量。
 *
 * @param queue 优先级队列指针
 * @param tag 指定TAG
 * @param free_data 是否释放节点数据
 *
 * @return 被删除节点的数量
 */
size_t pq_remove_all(tPRIORITY_QUEUE *queue, tQUEUE_TAG tag, bool free_data);

/**
 * @brief 遍历优先级队列
 *
 * 遍历给定的优先级队列，对每个元素执行指定的回调函数。
 *
 * @param queue 优先级队列指针
 * @param foreach 回调函数指针
 *
 * @return 遍历的元素数量
 */
size_t pq_foreach(tPRIORITY_QUEUE *queue, tQUEUE_FOREACH foreach);

/**
 * @brief 清空优先级队列
 *
 * 清空给定的优先级队列，并释放队列中的节点内存。
 *
 * @param queue 优先级队列指针
 * @param free_data 是否释放节点数据内存
 *
 * @return 成功删除的节点数量
 */
size_t pq_clear(tPRIORITY_QUEUE *queue, bool free_data);

#endif /* _PRIORITY_QUEUE_H_*/
